/**
 * @Question.Title: 柱状图中最大的矩形
 * @Question.No: 84
 * @Author: DQ
 * @Date: 2021-03-24 15:44:28
 * @Description: 
 */
//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 
//
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。 
//
// 
//
// 
//
// 以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。 
//
// 
//
// 
//
// 图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。 
//
// 
//
// 示例: 
//
// 输入: [2,1,5,6,2,3]
//输出: 10 
// Related Topics 栈 数组 
// 👍 1264 👎 0

package slidingwindows.leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

public class LargestRectangleInHistogram {
    public static void main(String[] args) {
        Solution solution = new LargestRectangleInHistogram().new Solution();
        int[] heights = {2,4,4};
        System.out.println(solution.largestRectangleArea(heights));
    }
        //leetcode submit region begin(Prohibit modification and deletion)
        class Solution {
            public int largestRectangleArea(int[] heights) {
                Deque<Integer> stack = new LinkedList<>();
                int ans = 0;
                int n = heights.length;
                for(int i = 0; i < n; i++){
                    if(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                        while(!stack.isEmpty() && heights[i] < heights[stack.peek()]){
                            int j = stack.pop();
                            while(!stack.isEmpty() && heights[stack.peek()] == heights[j]) j = stack.pop();
                            ans = Math.max(ans, (i-j) * heights[j]);
                        }
                    }
                    stack.push(i);
                }
                while(!stack.isEmpty()){
                    int j = stack.pop();
                    ans = Math.max((n-j) * heights[j], ans);
                }
                return ans;
            }
        }
//leetcode submit region end(Prohibit modification and deletion)

}